package main.adt.list;

/**
 * Created by july on 2015/12/12.
 * 线性表的链式存储---单链表
 * 基本操作：
 *  1、初始化一个空的链表
 *  2、以指定元素初始化链表
 *
 *  3、添加数据到链表表尾
 *  4、添加数据到链表指定位置
 *
 *  5、移除链表表尾部数据
 *  6、移除链表指定位置的数据
 *  7、清空链表
 *
 *  8、修改链表指定位置的数据
 *
 *  9、查询指定位置的数据
 *  10、查询指定数据在链表中首次出现的位置
 *
 *  11、获取链表中元素个数
 *  12、判断链表是否为空
 */
public class SingleLinkedList<E> {

    private int size;       //元素个数
    private Node header;    //头节点
    private Node tail;      //尾节点

    public SingleLinkedList() {
        header = tail = null;
    }

    public SingleLinkedList(E element){
        header = tail = new Node(element,null);
        size++;
    }

    /**
     * 添加数据到链表表尾
     * @param element
     * @return
     */
    public boolean add(E element){
      return  addAtTail(element);
    }

    /**
     * 在链表的指定位置插入数据
     * 链表中插入数据不同于顺序表的插入，顺序表的插入涉及到数据位置的移动，但链表中的插入不需要移动数据
     * 的位置，所以在插入操作比较频繁的时候，应该优先选择链表结构
     * @param index
     * @param element
     * @return
     */
    public boolean add(int index,E element){
        checkAddIndex(index);
        if(index == 0){
            addAtHeader(element);
        }else{
            Node preNode = getNodeByIndex(index - 1);
            preNode.next = new Node(element,preNode.next);
            size++;
        }
        return true;
    }

    /**
     * 从表尾移除数据。
     * @return
     */
    public E remove(){
       return removeByIndex(size - 1);
    }

    /**
     * 从指定位置处移除数据
     * logic:
     *  如果只有一个数据，直接调用清空方法
     *  如果有多条数据：
     *      如果是删除第一条数据，就直接让头节点指向原来头节点的直接后继
     *      如果是删除其他位置上的数据，先查询出当前数据的上一个节点，让上一个节点指向当前结点
     *      的直接后继
     * @return
     */
    public E removeByIndex(int index){
        checkIndex(index);
        Node node = getNodeByIndex(index);
        if(size == 1){
            clear();
        }else{
            if(index == 0){
                header = header.next;
            }else{
                Node preNode = getNodeByIndex(index - 1);
                preNode.next = node.next;
            }
            node.next = null;
            size--;
        }
        return node.data;
    }

    /**
     * 清空链表
     */
    public void clear(){
        header = tail = null;
        size = 0;
    }

    /**
     * 修改指定位置的数据
     * @param index
     * @param element
     * @return
     */
    public boolean set(int index,E element){
        checkIndex(index);
        Node node = getNodeByIndex(index);
        node.data = element;
        return true;
    }

    /**
     * 查询指定位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        return getNodeByIndex(index).data;
    }

    /**
     * 查询指定数据在链表中首次出现的位置，如果不存在返回-1
     * @param element
     * @return
     */
    public int indexOf(E element){
        int count = 0;
        for(Node current = header;current != null;current = current.next){
            if(element == null){
                if(current.data == null){
                    return count;
                }
            }else{
                if(element.equals(current.data)){
                    return count;
                }
            }
            count++;
        }
        return -1;
    }

    /**
     * 判断集合是否为空
     * @return true:空；false：不为空
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 获取集合中元素个数
     * @return
     */
    public int size(){
        return size;
    }

    /**
     *  复写toString方法，便于查看集合中的数据
     */
    @Override
    public String toString(){
        if(size == 0){
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        for(Node current = header;current != null;current = current.next){
            if(current.data != null){
                sb.append(current.data.toString()).append(",");
            }else{
                sb.append("Null").append(',');
            }
        }
        int len = sb.length();
        sb.delete(len-1,len).append("]");
        return sb.toString();
    }

    /**
     * 检查插入位置，插入位置不能小于0且不能大于集合中的元素个数
     * @param index
     */
    private void checkAddIndex(int index){
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("插入位置有误，当前集合元素个数为：" + size +" 插入位置却为：" + index +" 明显不对嘛");
        }
    }

    /**
     *检查查询位置
     * @param index
     */
    private void checkIndex(int index){
        if(index < 0 || index > size - 1){
            throw new IndexOutOfBoundsException("指定索引位置有误");
        }
    }

    /**
     * 头插法：
     * 该方法从一个空表开始，不断地创建新节点，将数据元素存入节点data域中，然后不断以新节点为头节点，
     * 让新节点指向原来的头节点，这种方法虽然实现起来比较简单方便，但生成的链表节点顺序和输入顺序相反。
     * @param element
     * @return
     */
    private boolean addAtHeader(E element){
        if(size == 0){
            header = tail = new Node(element,null);
        }else{
            header = new Node(element,header);
        }
        size++;
        return true;
    }

    /**
     * 尾插法：
     * 该方法是将新节点插入到当前链表的表尾上，因此需要为链表定义一个引用变量来保存链表的最后一个节点。
     * @param element
     * @return
     */
    private boolean addAtTail(E element){
        if(size == 0){
            header = tail = new Node(element,null);
        }else{
            Node newNode = new Node(element,null);
            tail.next = newNode;
            tail = newNode;
        }
        size++;
        return true;
    }

    /**
     * 查询指定位置的节点元素
     * 由于是单链表结构，节点只保留了直接后继的指针，所以在查找结点时，只能从头节点开始，依次查找
     * 后继节点，所以说节点越靠后，查找所需时间也越长。时间复杂度O(n);
     * @param index
     * @return
     */
    private Node getNodeByIndex(int index) {
        checkIndex(index);
        Node current = header;
        int count = 0;
        while(current != null){
            if(count == index){
                return current;
            }
            current = current.next;
            count++;
        }
        return null;
    }

    private class Node{
        private E data;      //数据域
        private Node next;   //指针域,指向它的直接后继

        protected Node(E element, Node next) {
            this.data = element;
            this.next = next;
        }
    }
}
